package bit_pratice.day5;

/**
 * @author 美女
 * @date 2022/05/04 19:52
 **/

/**
 * 连续子数组最大和
 * 动态规划解决
 */
import java.util.*;
public class Num2{
    public static int getMax(int a,int b){
        return a>b?a:b;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//数组元素个数
        int[] array=new int[n];
        for(int i=0;i<n;i++){
            //给数组元素赋值
            array[i]=sc.nextInt();
        }
        //将0位置索引值作为初始值，i从1开始
        //当前子数组的和
        int sum=array[0];
        //连续子数组最大和——最终要输出的结果
        int max=array[0];
        for(int i=1;i<n;i++){
            //获取arr[i]+sum(以i-1结尾的数组的最大和)与arr[i]的较大值
            //初始以i-1结尾的数组的最大和就是array[0]
            sum=getMax(sum+array[i],array[i]);
            //判断此时的sum和max哪一个大
            if(sum>=max){
                max=sum;
            }
        }
        System.out.println(max);
    }
}
